{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二叉树的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 二叉树的节点\n",
    "class TreeNode(object):\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.val = val\n",
    "\n",
    "# 二叉树\n",
    "class BinaryTree(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "    \n",
    "    # 前序遍历（深度优先）\n",
    "    def preorder_traversal(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        left = self.preorder_traversal(root.left)\n",
    "        right = self.preorder_traversal(root.right)\n",
    "        return [root.val] + left + right\n",
    "    \n",
    "    # 中序遍历（深度优先）\n",
    "    def inorder_traversal(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        left = self.inorder_traversal(root.left)\n",
    "        right = self.inorder_traversal(root.right)\n",
    "        return left + [root.val] + right\n",
    "    \n",
    "    # 后序遍历（深度优先）\n",
    "    def postorder_traversal(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        left = self.postorder_traversal(root.left)\n",
    "        right = self.postorder_traversal(root.right)\n",
    "        return left + right + [root.val]\n",
    "    \n",
    "    # 广度优先遍历，用队列实现\n",
    "    def bfs(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        vals = []\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            vals.append(node.val)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "        return vals\n",
    "    \n",
    "    # 深度优先遍历，用栈实现\n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        stack = [root]\n",
    "        vals = []\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            vals.append(node.val)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "        return vals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(1)\n",
    "tree.root.left = TreeNode(2, TreeNode(4), TreeNode(5))\n",
    "tree.root.right = TreeNode(3, None, TreeNode(7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#     1\n",
    "#    / \\\n",
    "#   2  3\n",
    "#  /\\   \\\n",
    "# 4 5   7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4, 5, 3, 7]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.preorder_traversal(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 2, 5, 1, 3, 7]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.inorder_traversal(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 5, 2, 7, 3, 1]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.postorder_traversal(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.inorder_traversal(None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 7]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.bfs(None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4, 5, 3, 7]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.dfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.dfs(None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 105. 从前序与中序遍历序列构造二叉树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 根据一棵树的前序遍历与中序遍历构造二叉树。\n",
    "\n",
    "# 注意:\n",
    "# 你可以假设树中没有重复的元素。\n",
    "\n",
    "# 例如，给出\n",
    "\n",
    "# 前序遍历 preorder = [3,9,20,15,7]\n",
    "\n",
    "# 中序遍历 inorder = [9,3,15,20,7]\n",
    "\n",
    "# 返回如下的二叉树：\n",
    "#     3\n",
    "#    / \\\n",
    "#   9  20\n",
    "#     /  \\\n",
    "#    15   7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# preorder的第一个节点为根节点，在inorder中寻找根节点，将inorder分割为左子树inorder和右子树inorder\n",
    "def build_tree(preoder, inorder):\n",
    "    if not preoder:\n",
    "        return None\n",
    "    root_val = preoder[0]\n",
    "    idx = inorder.index(root_val)\n",
    "    left = build_tree(preoder[1:idx + 1], inorder[:idx])\n",
    "    right = build_tree(preoder[idx + 1:], inorder[idx + 1:])\n",
    "    root = TreeNode(root_val, left, right)\n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 9, 20, 15, 7]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = build_tree([3,9,20,15,7], [9,3,15,20,7])\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = build_tree([3], [3])\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = build_tree([1,2,3,4], [4,3,2,1])\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = build_tree([1,2,4,6,3,5,7], [2,6,4,1,3,7,5])\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 236. 二叉树的最近公共祖先"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。\n",
    "\n",
    "百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”\n",
    "\n",
    "例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]\n",
    "\n",
    "<img src=\"images/binarytree.png\">\n",
    "\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1\n",
    "输出: 3\n",
    "\n",
    "解释: 节点 5 和节点 1 的最近公共祖先是节点 3。\n",
    "示例 2:\n",
    "\n",
    "输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4\n",
    "输出: 5\n",
    "\n",
    "解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。\n",
    " \n",
    "\n",
    "说明:\n",
    "\n",
    "所有节点的值都是唯一的。\n",
    "p、q 为不同节点且均存在于给定的二叉树中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lowest_common_ancestor(root, p, q):\n",
    "    queue = [root]\n",
    "    node_dict = {root:None}\n",
    "    while queue:\n",
    "        node = queue.pop(0)\n",
    "        if node.left:\n",
    "            node_dict[node.left] = node\n",
    "            queue.append(node.left)\n",
    "        if node.right:\n",
    "            node_dict[node.right] = node\n",
    "            queue.append(node.right)\n",
    "    a = p\n",
    "    b = q\n",
    "    while a != b:\n",
    "        a = node_dict[a] if a else q\n",
    "        b = node_dict[b] if b else p\n",
    "    return a.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5, 1, 6, 2, 0, 8, 7, 4]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(3)\n",
    "tree.root.left = TreeNode(5, TreeNode(6), TreeNode(2, TreeNode(7), TreeNode(4)))\n",
    "tree.root.right = TreeNode(1, TreeNode(0), TreeNode(8))\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lowest_common_ancestor(tree.root, tree.root.left, tree.root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lowest_common_ancestor(tree.root, tree.root.left, tree.root.left.right.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lowest_common_ancestor(tree.root, tree.root.left.right.left, tree.root.left.right.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lowest_common_ancestor(tree.root, tree.root, tree.root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 递归解法\n",
    "# 在左、右子树中分别查找是否包含p或q，如果左右子树各包含一个p或q，那么此时的根节点就是最近公共祖先\n",
    "# 如果左子树包含p和q，那么到左子树中查找，最近公共祖先在左子树里面\n",
    "# 如果右子树包含p和q，那么到右子树中查找，最近公共祖先在右子树里面\n",
    "def lowest_common_ancestor2(node, p, q):\n",
    "    if not node or node == p or node == q:\n",
    "        return node\n",
    "    left = lowest_common_ancestor2(node.left, p, q)\n",
    "    right = lowest_common_ancestor2(node.right, p, q)\n",
    "    if not left: return right\n",
    "    if not right: return left\n",
    "    return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5, 1, 6, 2, 0, 8, 7, 4]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(3)\n",
    "tree.root.left = TreeNode(5, TreeNode(6), TreeNode(2, TreeNode(7), TreeNode(4)))\n",
    "tree.root.right = TreeNode(1, TreeNode(0), TreeNode(8))\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lowest_common_ancestor2(tree.root, tree.root.left, tree.root.right).val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lowest_common_ancestor2(tree.root, tree.root.left, tree.root.left.right.right).val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lowest_common_ancestor2(tree.root, tree.root.left.right.left, tree.root.left.right.right).val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lowest_common_ancestor2(tree.root, tree.root, tree.root.left).val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 100. 相同的树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 给定两个二叉树，编写一个函数来检验它们是否相同。\n",
    "\n",
    "# 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。\n",
    "\n",
    "# 示例 1:\n",
    "\n",
    "# 输入:       1         1\n",
    "#           / \\       / \\\n",
    "#          2   3     2   3\n",
    "\n",
    "#         [1,2,3],   [1,2,3]\n",
    "\n",
    "# 输出: true\n",
    "    \n",
    "# 示例 2:\n",
    "\n",
    "# 输入:      1          1\n",
    "#           /           \\\n",
    "#          2             2\n",
    "\n",
    "#         [1,2],     [1,null,2]\n",
    "\n",
    "# 输出: false\n",
    "    \n",
    "# 示例 3:\n",
    "\n",
    "# 输入:       1         1\n",
    "#           / \\       / \\\n",
    "#          2   1     1   2\n",
    "\n",
    "#         [1,2,1],   [1,1,2]\n",
    "\n",
    "# 输出: false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 递归实现\n",
    "def is_same_tree(p, q):\n",
    "    if not p and not q:\n",
    "        return True\n",
    "    if not p or not q:\n",
    "        return False\n",
    "    if p.val != q.val:\n",
    "        return False\n",
    "    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree1 = BinaryTree()\n",
    "tree1.root = TreeNode(1)\n",
    "tree1.root.left = TreeNode(2)\n",
    "tree1.root.right = TreeNode(3)\n",
    "\n",
    "tree2 = BinaryTree()\n",
    "tree2.root = TreeNode(1)\n",
    "tree2.root.left = TreeNode(2)\n",
    "tree2.root.right = TreeNode(3)\n",
    "\n",
    "is_same_tree(tree1.root, tree2.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree1 = BinaryTree()\n",
    "tree1.root = TreeNode(1)\n",
    "tree1.root.left = TreeNode(2)\n",
    "\n",
    "tree2 = BinaryTree()\n",
    "tree2.root = TreeNode(1)\n",
    "tree2.root.right = TreeNode(2)\n",
    "\n",
    "is_same_tree(tree1.root, tree2.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree1 = BinaryTree()\n",
    "tree1.root = TreeNode(1)\n",
    "tree1.root.left = TreeNode(2)\n",
    "tree1.root.right = TreeNode(1)\n",
    "\n",
    "tree2 = BinaryTree()\n",
    "tree2.root = TreeNode(1)\n",
    "tree2.root.left = TreeNode(1)\n",
    "tree2.root.right = TreeNode(2)\n",
    "\n",
    "is_same_tree(tree1.root, tree2.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree1 = BinaryTree()\n",
    "tree1.root = TreeNode(1)\n",
    "\n",
    "tree2 = BinaryTree()\n",
    "\n",
    "is_same_tree(tree1.root, tree2.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree1 = BinaryTree()\n",
    "\n",
    "tree2 = BinaryTree()\n",
    "\n",
    "is_same_tree(tree1.root, tree2.root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 111. 二叉树的最小深度"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 给定一个二叉树，找出其最小深度。\n",
    "\n",
    "# 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。\n",
    "\n",
    "# 说明: 叶子节点是指没有子节点的节点。\n",
    "\n",
    "# 示例:\n",
    "\n",
    "# 给定二叉树 [3,9,20,null,null,15,7],\n",
    "\n",
    "#     3\n",
    "#    / \\\n",
    "#   9  20\n",
    "#     /  \\\n",
    "#    15   7\n",
    "# 返回它的最小深度  2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 递归实现\n",
    "def min_depth(root):\n",
    "    if not root:\n",
    "        return 0\n",
    "    if root.left and root.right:\n",
    "        return 1 + min(min_depth(root.left), min_depth(root.right))\n",
    "    if root.left:\n",
    "        return 1 + min_depth(root.left)\n",
    "    if root.right:\n",
    "        return 1 + min_depth(root.right)\n",
    "    return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 9, 20, 15, 7]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(3)\n",
    "tree.root.left = TreeNode(9)\n",
    "tree.root.right = TreeNode(20, TreeNode(15), TreeNode(7))\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 9]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(3)\n",
    "tree.root.left = TreeNode(9)\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(3)\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 广度优先搜索，用队列实现\n",
    "def min_depth2(root):\n",
    "    if not root:\n",
    "        return 0\n",
    "    queue = [root]\n",
    "    depth = 1\n",
    "    while queue:\n",
    "        node = queue.pop(0)\n",
    "        if not node.left and not node.right:\n",
    "            return depth\n",
    "        if node.left:\n",
    "            queue.append(node.left)\n",
    "        if node.right:\n",
    "            queue.append(node.right)\n",
    "        depth += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 9, 20, 15, 7]"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(3)\n",
    "tree.root.left = TreeNode(9)\n",
    "tree.root.right = TreeNode(20, TreeNode(15), TreeNode(7))\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth2(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 9]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(3)\n",
    "tree.root.left = TreeNode(9)\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth2(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3]"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(3)\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth2(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth2(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 深度优先搜索，用栈实现\n",
    "def min_depth3(root):\n",
    "    if not root:\n",
    "        return 0\n",
    "    stack = [(root, 1)]\n",
    "    min_depth = float('inf')\n",
    "    while stack:\n",
    "        node, depth = stack.pop()\n",
    "        if not node.left and not node.right:\n",
    "            min_depth = min(min_depth, depth)\n",
    "        if node.right:\n",
    "            stack.append((node.right, depth + 1))\n",
    "        if node.left:\n",
    "            stack.append((node.left, depth + 1))\n",
    "    return min_depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 9, 20, 15, 7]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(3)\n",
    "tree.root.left = TreeNode(9)\n",
    "tree.root.right = TreeNode(20, TreeNode(15), TreeNode(7))\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth3(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 9]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(3)\n",
    "tree.root.left = TreeNode(9)\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth3(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3]"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.root = TreeNode(3)\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth3(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinaryTree()\n",
    "tree.bfs(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_depth3(tree.root)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3(py37)",
   "language": "python",
   "name": "py37"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
